\documentclass{ctexart}
\usepackage{graphicx} %插入图片的宏包
\usepackage{diagbox}
\usepackage{float} %设置图片浮动位置的宏包
\usepackage{subfigure}
\usepackage{amsmath}
\title{Numerical Analysis Ex6}
\date{27-12-2022}
\author{王惠恒 3200300395}
\usepackage{geometry}
 \geometry{
 a4paper,
 total={170mm,257mm},
 left=20mm,
 top=5mm,
 }
\begin{document}
\maketitle
\textbf{I}:
(a)Given that Simpson's rule can be expressed as $I^S(f)=\frac{b-a}{6}[f(a)+4f(\frac{a+b}{2})+f(b)]$,thus we easily get Simpson's rule on $[-1,1]$ is 
$$I^S(f)=\frac{1}{3}[f(-1)+4f(0)+f(1)]$$
According to the given points, we use Hermite interpolation to give the expression of $p_3(y;,-1,0,0,1;t)$.
\begin{table}[!htbp]
    \centering
    \begin{tabular}{|c|c|c|c|c|}
    \hline
    $x_1=-1$&$y(-1)$&-&-&-\\
    \hline
    $x_2=0$&$y(0)$&$y(0)-y(-1)$&-&-\\
    \hline 
    $x_3=0$&$y(0)$&$y'(0)$&$y'(0)-y(0)+y(-1)$&-\\
    \hline
    $x_4=1$&$y(1)$&$y(1)-y(0)$&$y(1)-y(0)-y'(0)$&$\frac{1}{2}[y(1)-y(-1)-2y'(0)]$\\
    \hline
    \end{tabular}
\end{table}

    $$p_3(y;-1,0,0,1;t)=y(-1)+[y(0)-y(-1)](t+1)+[y'(0)-y(0)+y(-1)]t(t+1)+\frac{1}{2}[y(1)-y(-1)-2y'(0)]t^2(t+1)$$
    \begin{align*}
    \int_{-1}^{1} p_3(y;-1,0,0,1;t) dt&=\int_{-1}^{1} y(0)+y'(0)t+\frac{y(-1)+y(1)-2y(0)}{2}t^2+\frac{y(1)-2y'(0)-f(-1)}{2}t^3 dt \\
    &=\frac{1}{3}[y(-1)+4y(0)+y(1)]
\end{align*}
where $y=f(x)$,then it is proven.\\
(b)
\begin{align*}
    E^S(y)&=\int_{-1}^{1}y(t)dt-\int_{-1}^{1} p_3(y;-1,0,0,1;t) dt\\
    &=\int_{-1}^{1} \frac{f^{(4)}(\xi)}{4!}t^2(t^2-1) dt\\
    &=\frac{f^{(4)}(\zeta)}{4!}\int_{-1}^{1}(t^4-t^2) dt\\
    &=-\frac{f^{(4)}(\zeta)}{90}
\end{align*}
where $\xi,\zeta \in (-1,1)$\\
(c)Let $x=\frac{b-a}{2}t+\frac{b+a}{2}$,then
\begin{align*}
    \int_{a}^{b}y(t) dt&=\int_{-1}^{1}y(\frac{b-a}{2}t+\frac{b+a}{2}) \frac{b-a}{2} dt\\
    &=\int_{a}^{b}p_3(y;a,\frac{a+b}{2},\frac{a+b}{2},b;t) dt +E^S\\
    &=\frac{b-a}{6}[f(a)+4f(\frac{a+b}{2})+f(b)]+E^S\\
    E^S&=\int_{a}^{b}[y(t)-p_3(y;a,\frac{a+b}{2},\frac{a+b}{2},b;t)] dt\\
    &=\int_{a}^{b}\frac{f^{(4)}(\xi)}{4!}(t-a)(t-\frac{a+b}{2})^2(t-b) dt\\
    &=-\frac{(b-a)^5}{2880}f^{(4)}(\xi)\\
\end{align*}
where $\xi \in (a,b)$.Then we take $x_k=a+kh,h=\frac{b-a}{n}$,and $n$ is even.Thus we have $$I_n^S(f)=\frac{h}{3}[f(x_0)+4f(x_1)+2f(x_2)+4f(x_3)+2f(x_4)+...+4f(x_{n-1})+f(x_n)]$$
$$E_n^S(f)=\sum_{k=1}^{\frac{n}{2}}E_k^S(f)=\sum_{k=1}^{\frac{n}{2}}-\frac{(2h)^5}{2880}f^{(4)}(\xi_k)=-\frac{h^5}{90}[\frac{b-a}{2h}f^{(4)}(\xi)])=-\frac{b-a}{180}h^4f^{(4)}(\xi)$$
where $a=x_0<x_1<...<x_n=b,\xi_k \in (x_k,x_{k+1}),\xi \in (a,b)$\\

\textbf{II}:Let $$f(x)=e^{-x^2}$$$$f'(x)=-2xe^{-x^2}$$$$f''(x)=4x^2e^{-x^2}-2e^{-x^2}=e^{-x^2}(4x^2-2)$$$$f'''(x)=8xe^{-x^2}+(-8x^3+4x)e^{-x^2}=e^{-x^2}(-8x^3+12x)$$$$f^{(4)}(x)=(-24x^2+12)e^{-x^2}+e^{-x^2}(16x^4-24x^2)=e^{-x^2}(16x^4-48x^2+12)$$$$f^{(5)}(x)=e^{-x^2}(64x^3-96x)+(-32x^5+96x^3-24x)e^{-x^2}=e^{-x^2}(-32x^5+160x^3-120x)$$
As $f''(x)$ is continuous and monotonically increasing in $[0,1] $,then $|f''(x)|\leq 2e^{-1}$.Besides,$f^{(4)}(x)$ reaches the maximum value at $x=0$,$|f^{(4)}(x)|\leq12$\\
(a)By the absolute error of the composite trapezoidal rule:
$$|E_n^T(f)|=|-\frac{b-a}{12}h^2f''(\xi)|=|\frac{1}{12}\cdot \frac{1}{n^2} f''(\xi)|\leq \frac{1}{6n^2e}<0.5 \times 10^{-6}$$
$\Rightarrow n \geq 350$\\
(b)By the absolute error of the composite Simpson's rule:
$$|E_n^S(f)|=|-\frac{b-a}{180}h^4f^{(4)}(\xi)|=|\frac{1}{180}\cdot \frac{1}{n^2}f^{(4)}(\xi)|\leq \frac{1}{15n^4}<0.5 \times 10^{-6}$$\\
$\Rightarrow n \geq 19$\\

\textbf{III}:(a)$\pi_2(t)=t^2+at+b$,and by the hint $\int_{0}^{+\infty} t^me^{-t}dt=m!$
\begin{align*}
    <\pi_2,1>&=\int_{0}^{+\infty}(t^2+at+b)e^{-t} dt=0 \Rightarrow 2+a+b=0\\
    <\pi_2,t>&=\int_{0}^{+\infty}t(t^2+at+b)e^{-t} dt=0 \Rightarrow 6+2a+b=0
\end{align*}
we can solve $a=-4,b=2 \Rightarrow \pi_2(t)=t^2-4t+2$.\\
(b)Let $\pi_2(t)=0 \Rightarrow t_1=2-\sqrt{2},t_2=2+\sqrt{2}$.Then we have 
\begin{align*}
    w_1+w_2&=\int_{0}^{+\infty} e^{-t} dt=1\\
    t_1w_1+t_2w_2&=\int_{0}^{+\infty} te^{-t} dt=1
\end{align*}
we can solve $w_1=\frac{t_2-1}{t_2-t_1}=\frac{1+\sqrt{2}}{2\sqrt{2}},w_2=\frac{1-t_1}{t_2-t_1}=\frac{\sqrt{2}-1}{2\sqrt{2}}$.
Then
\begin{align*}
    I_2^G&=\int_{0}^{+\infty} e^{-t}f(t)dt=w_1f(t_1)+w_2f(t_2)+E_2(f)\\
    &=\frac{1+\sqrt{2}}{2\sqrt{2}}f(2-\sqrt{2})+\frac{\sqrt{2}-1}{2\sqrt{2}}f(2+\sqrt{2})+E_2(f)\\
\end{align*}
By theorem 6.35,
$$E_n^{G}(f)=\frac{f^{(2n)}(\xi)}{(2n)!}\int_{a}^{b}\rho(x)v_n^2(x) dx$$
\begin{align*}
    E_2(f)&=\frac{f^{(4)}(\xi)}{4!}\int_{0}^{+\infty} e^{-t}\pi_2^2(t) dt\\
    &=\frac{f^{(4)}(\xi)}{4!}\int_{0}^{+\infty} e^{-t}(t^4-8t^3+20t^2-16t+4) dt\\
    &=\frac{f^{(4)}(\xi)}{3!}
\end{align*}
where $\xi \in (0,+\infty)$\\
(c)
\begin{align*}
    E_2(f)&=\frac{\frac{24}{(1+\xi)^5}}{3!}=\frac{4}{(1+\xi)^5}\\
    I^G(f)&=\frac{w_1}{1+t_1}+\frac{w_2}{1+t_2}=\frac{4}{7}
\end{align*}
Then the exact error is $I(f)-I^G(f)=0.024918789...=\frac{4}{(1+\xi)^5}$,by solving it, $\xi\approx 1.7613$\\

\textbf{IV}:
(a)Given that $p(x_m)=f_m,p'(x_m)=f_m'$,and also 
$$p(t)=\sum_{m=1}^{n}[h_m(t)f_m+q_m(t)f_m']$$
where $h_m(t)=(a_m+b_mt)l_m^2(t),q_m(t)=(c_m+d_mt)l_m^2(t)$,$l_m$ is a lagrange polynomial.Now we derive $a_m,b_m,c_m,d_m$.
\begin{align*}
    h_m(x_m)&=a_m+b_mx_m=1\\
    h_m'(x_m)&=b_m+2(a_m+b_mx_m)l_m'(x_m)=0\\
    q_m(x_m)&=x_m+d_mx_m=1\\
    q_m'(x_m)&=d_m+2(x_m+d_mx_m)l_m'(x_m)=0\\
    l_m'(x_m)&=\sum_{i=1,i \neq m}^{n} \frac{1}{x_m-x_i}\\
\end{align*}
By solving them,we can get 
$$a_m=1+2x_m\sum_{i=1,i \neq m}^{n} \frac{1}{x_m-x_i},b_m=-2\sum_{i=1,i \neq m}^{n} \frac{1}{x_m-x_i},c_m=-x_m,d_m=1$$
for $\forall m=1,2,...,n$\\
(b)\begin{align*}
    I_n(f)=I_n(p(f))&=\int_{a}^{b}\rho(t)
    \sum_{k=1}^{n}(h_kf_k+q_kf_k') dt\\
    &=\sum_{k=1}^{n}[f(x_k)\int_{a}^{b}\rho(t)h_k(t) dt+f'(x_k)\int_{a}^{b}\rho(t)q_k(t)dt]
    :=\sum_{k=1}^{n}[w_kf(x_k)+\mu_kf'(x_k)]
\end{align*}
where
\begin{align*}
    w_k&=\int_{a}^{b}\rho(t)h_k(t)dt]\\
    \mu_k&=\int_{a}^{b}\rho(t)q_k(t) dt
\end{align*}
(c)If $\mu_k=\int_{a}^{b}\rho(t)q_k(t) dt=0$,which means $\int_{a}^{b}\rho(t)v_n(t)l_k(t) dt=0,\>\>\>\> \forall k=1,2,...,n$\\
As $\textbf{P}_{n-1}=span\{l_1,l_2,...,l_n\}=span\{1,t,...,t^{n-1}\}$,thus the condition is 
$$\int_{a}^{b} \rho(t)v_n(t)p(t) dt=0$$\\

\textbf{V}:Given that $D^2u(\bar x)=\frac{u(\bar x-h)-2u(\bar x)+u(\bar x+h)}{h^2}$.
\begin{align*}
   u(\bar x-h)&=u(\bar x)-hu'(\bar x)+\frac{1}{2}h^2u''(\bar x)-\frac{1}{6}h^3u'''(\bar x)+\frac{1}{24}h^4u^{(4)}(\xi_1)\\
   u(\bar x+h)&=u(\bar x)+hu'(\bar x)+\frac{1}{2}h^2u''(\bar x)+\frac{1}{6}h^3u'''(\bar x)+\frac{1}{24}h^4u^{(4)}(\xi_2)
\end{align*}
where $\xi_1 \in (\bar x-h,\bar x),\xi_2 \in (\bar x,\bar x+h)$.Then 
$$D^2u(\bar x)=u''(\bar x)+\frac{1}{24}h^2(u^{(4)}(\xi_1)+u^{(4)}(\xi_2))=u''(\bar x)+O(h^2)$$
Thus,$D^2u(\bar x)$ is second-order accurate.Now we have a perturb with random errors $\epsilon \in [-E,E]$,let 
\begin{align*}
    \hat{u}(\bar x-h)&=u(\bar x-h)+\epsilon_1=u(\bar x)-u'(\bar x)h+\frac{u''(\bar x)}{2}h^2-\frac{u'''(\bar x)}{6}h^3+\frac{u^{(4)}(\xi_1)}{24}h^4+\epsilon_1\>\>\>\>(1)\\
    \hat{u}(\bar x+h)&=u(\bar x+h)+\epsilon_2=u(\bar x)+u'(\bar x)h+\frac{u''(\bar x)}{2}h^2+\frac{u'''(\bar x)}{6}h^3+\frac{u^{(4)}(\xi_2)}{24}h^4+\epsilon_2\>\>\>\>(2)\\
    \hat{u}(\bar x)&=u(\bar x)+\epsilon_3\>\>\>\>(3)
\end{align*}
Then $\frac{(1)-2(3)+(2)}{h^2} \Rightarrow D^2u(\bar x)=u''(\bar x)+\frac{h^2}{12}u^{(4)}(\xi)+\frac{\epsilon_1-2\epsilon_3+\epsilon_2}{h^2}$.By triangle inequality,
$$|u''(\bar x)-D^2u(\bar x)|\leq \frac{h^2}{12}|u^{(4)}(\xi)|+\frac{4E}{h^2},\xi \in (\bar x-h,\bar x+h)$$
To find a fourth-order accurate formula,we can take the relation among $u(\bar x-2h),u(\bar x-h),u(\bar x),u(\bar x+h),u(\bar x+2h)$.
\begin{align*}
    u(\bar x-2h)+u(\bar x+2h)&=2u(\bar x)+4h^2u''(\bar x)+\frac{4}{3}h^4u^{(4)}(\bar x)+\frac{8}{45}h^6u^{(6)}(\xi_1),\xi_1 \in (\bar x-2h,\bar x+2h)\\
    u(\bar x-h)+u(\bar x+h)&=2u(\bar x)+h^2u''(\bar x)+\frac{1}{12}h^4u^{(4)}(\bar x)+\frac{1}{360}h^6u^{(6)}(\xi_2),\xi_2 \in (\bar x-h,\bar x+h)
\end{align*}
Then we have 
\begin{align*}
    u''(\bar x)&=\frac{-u(\bar x-2h)+16u(\bar x-h)-30u(\bar x)+16u(\bar x+h)-u(\bar x+2h)}{12h^2}+\frac{h^4}{540}[8u^{(6)}(\xi_1)-2u^{(6)}(\xi_2)]\\
    &=D^4u(\bar x)+O(h^4)\\
    |u''(\bar x)-D^4u(\bar x)|& \leq \frac{h^4}{54}|u^{(6)}(x)|+\frac{16E}{3h^2}
\end{align*}
To minimize the error bound, 
\begin{align*}
    \frac{h^4}{54}|u^{(6)}(x)|+\frac{16E}{3h^2}&=0\\
    h&=\sqrt[6]{\frac{144E}{|u^{(6)}(x)|}}
\end{align*}
It is necessary to reach higher order accuracy with more initial points.
\end{document}